home *** CD-ROM | disk | FTP | other *** search
/ Personal Computer World 2009 February / PCWFEB09.iso / Software / Linux / SLAX 6.0.8 / slax-6.0.8.iso / slax / base / 006-devel.lzm / usr / include / isc / heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  2008-09-17  |  5.6 KB  |  171 lines
  1. /*
  2.  * Copyright (C) 2004-2006  Internet Systems Consortium, Inc. ("ISC")
  3.  * Copyright (C) 1997-2001  Internet Software Consortium.
  4.  *
  5.  * Permission to use, copy, modify, and distribute this software for any
  6.  * purpose with or without fee is hereby granted, provided that the above
  7.  * copyright notice and this permission notice appear in all copies.
  8.  *
  9.  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10.  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11.  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12.  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13.  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14.  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15.  * PERFORMANCE OF THIS SOFTWARE.
  16.  */
  17.  
  18. /* $Id: heap.h,v 1.17.18.3 2006/04/17 18:27:33 explorer Exp $ */
  19.  
  20. #ifndef ISC_HEAP_H
  21. #define ISC_HEAP_H 1
  22.  
  23. /*! \file */
  24.  
  25. #include <isc/lang.h>
  26. #include <isc/types.h>
  27.  
  28. ISC_LANG_BEGINDECLS
  29.  
  30. /*%
  31.  * The comparision function returns ISC_TRUE if the first argument has
  32.  * higher priority than the second argument, and ISC_FALSE otherwise.
  33.  */
  34. typedef isc_boolean_t (*isc_heapcompare_t)(void *, void *);
  35.  
  36. /*%
  37.  * The index function allows the client of the heap to receive a callback
  38.  * when an item's index number changes.  This allows it to maintain
  39.  * sync with its external state, but still delete itself, since deletions
  40.  * from the heap require the index be provided.
  41.  */
  42. typedef void (*isc_heapindex_t)(void *, unsigned int);
  43.  
  44. /*%
  45.  * The heapaction function is used when iterating over the heap.
  46.  *
  47.  * NOTE:  The heap structure CANNOT BE MODIFIED during the call to
  48.  * isc_heap_foreach().
  49.  */
  50. typedef void (*isc_heapaction_t)(void *, void *);
  51.  
  52. typedef struct isc_heap isc_heap_t;
  53.  
  54. isc_result_t
  55. isc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare,
  56.         isc_heapindex_t index, unsigned int size_increment,
  57.         isc_heap_t **heapp);
  58. /*!<
  59.  * \brief Create a new heap.  The heap is implemented using a space-efficient
  60.  * storage method.  When the heap elements are deleted space is not freed
  61.  * but will be reused when new elements are inserted.
  62.  *
  63.  * Requires:
  64.  *\li    "mctx" is valid.
  65.  *\li    "compare" is a function which takes two void * arguments and
  66.  *    returns ISC_TRUE if the first argument has a higher priority than
  67.  *    the second, and ISC_FALSE otherwise.
  68.  *\li    "index" is a function which takes a void *, and an unsigned int
  69.  *    argument.  This function will be called whenever an element's
  70.  *    index value changes, so it may continue to delete itself from the
  71.  *    heap.  This option may be NULL if this functionality is unneeded.
  72.  *\li    "size_increment" is a hint about how large the heap should grow
  73.  *    when resizing is needed.  If this is 0, a default size will be
  74.  *    used, which is currently 1024, allowing space for an additional 1024
  75.  *    heap elements to be inserted before adding more space.
  76.  *\li    "heapp" is not NULL, and "*heap" is NULL.
  77.  *
  78.  * Returns:
  79.  *\li    ISC_R_SUCCESS        - success
  80.  *\li    ISC_R_NOMEMORY        - insufficient memory
  81.  */
  82.  
  83. void
  84. isc_heap_destroy(isc_heap_t **heapp);
  85. /*!<
  86.  * \brief Destroys a heap.
  87.  *
  88.  * Requires:
  89.  *\li    "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  90.  */
  91.  
  92. isc_result_t
  93. isc_heap_insert(isc_heap_t *heap, void *elt);
  94. /*!<
  95.  * \brief Inserts a new element into a heap.
  96.  *
  97.  * Requires:
  98.  *\li    "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  99.  */
  100.  
  101. void
  102. isc_heap_delete(isc_heap_t *heap, unsigned int index);
  103. /*!<
  104.  * \brief Deletes an element from a heap, by element index.
  105.  *
  106.  * Requires:
  107.  *\li    "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  108.  *\li    "index" is a valid element index, as provided by the "index" callback
  109.  *    provided during heap creation.
  110.  */
  111.  
  112. void
  113. isc_heap_increased(isc_heap_t *heap, unsigned int index);
  114. /*!<
  115.  * \brief Indicates to the heap that an element's priority has increased.
  116.  * This function MUST be called whenever an element has increased in priority.
  117.  *
  118.  * Requires:
  119.  *\li    "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  120.  *\li    "index" is a valid element index, as provided by the "index" callback
  121.  *    provided during heap creation.
  122.  */
  123.  
  124. void
  125. isc_heap_decreased(isc_heap_t *heap, unsigned int index);
  126. /*!<
  127.  * \brief Indicates to the heap that an element's priority has decreased.
  128.  * This function MUST be called whenever an element has decreased in priority.
  129.  *
  130.  * Requires:
  131.  *\li    "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  132.  *\li    "index" is a valid element index, as provided by the "index" callback
  133.  *    provided during heap creation.
  134.  */
  135.  
  136. void *
  137. isc_heap_element(isc_heap_t *heap, unsigned int index);
  138. /*!<
  139.  * \brief Returns the element for a specific element index.
  140.  *
  141.  * Requires:
  142.  *\li    "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  143.  *\li    "index" is a valid element index, as provided by the "index" callback
  144.  *    provided during heap creation.
  145.  *
  146.  * Returns:
  147.  *\li    A pointer to the element for the element index.
  148.  */
  149.  
  150. void
  151. isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap);
  152. /*!<
  153.  * \brief Iterate over the heap, calling an action for each element.  The
  154.  * order of iteration is not sorted.
  155.  *
  156.  * Requires:
  157.  *\li    "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  158.  *\li    "action" is not NULL, and is a function which takes two arguments.
  159.  *    The first is a void *, representing the element, and the second is
  160.  *    "uap" as provided to isc_heap_foreach.
  161.  *\li    "uap" is a caller-provided argument, and may be NULL.
  162.  *
  163.  * Note:
  164.  *\li    The heap structure CANNOT be modified during this iteration.  The only
  165.  *    safe function to call while iterating the heap is isc_heap_element().
  166.  */
  167.  
  168. ISC_LANG_ENDDECLS
  169.  
  170. #endif /* ISC_HEAP_H */
  171.